\include{../../2.5/src/preamble}

\begin{document}
\ticket{2.9. Разрешимость языков}
\section{Разрешимые и перечислимые языки. Неразрешимые проблемы}
\begin{define}
  Язык $L$ называется рекурсивно-перечислимым, если $L=L(M)$ для
  некоторой МТ $M$, то есть для $\forall\omega\in L$ $M$ попадает в
  допускающее состояние на входе $\omega$.
\end{define}
\begin{define}
  Язык $L$ называется рекурсивным, если $L=L(M)$ для некоторой МТ $M$,
  удовлетворяющей следующим условиям:
  \begin{enumerate}
  \item Если $\omega\in L$, то $M$ попадает в допускающее
    состояние (и, следовательно, останавливается).
  \item Если $\omega\notin L$, то $M$  конце концов
    останавливается, хотя и не попадает в допускающее состояние.
  \end{enumerate}
\end{define}

Таким образом, существует три основных класса языков:
\begin{enumerate}
\item Рекурсивные языки.
\item Языки, которые рекурсивно перечислимы, но не рекурсивны.
\item Неперечислимые языки.
\end{enumerate}


Если мы рассматриваем язык $L$ как ``проблему'', то проблема $L$
называется \emph{разрешимой}, если она является рекурсивным языком. В
противном случае проблема называется \emph{неразрешимой}.
\section{Проблема останова}
Для МТ $M$ можно определить $H(M)$ как множество входов $\omega$, на
которых $M$ останавливается независимо от того, допускает ли $M$ вход
$\omega$.
Тогда \emph{проблема останова} состоит в определении множества таких
пар $(M, \omega)$, для которых $\omega\in H(M)$. Проблема останова
является примером рекурсивно-перечислимого, но не рекурсивного языка.
\section{Теорема Райса}
\begin{define}
  Свойство РП-языков представляет собой некоторое множество РП-языков.
\end{define}
Таким образом, формально свойство языка быть контекстно-свободным ---
это множество всех КС-языков. Свойство языка быть пустым есть
множество $\{\varnothing\}$, содержащее только пустой язык.
\begin{define}
  Свойство называется тривиальным, если оно либо пустое (т.е. никакой
  язык вообще ему не удовлетворяет), либо содержит все РП-языки. В
  противном случае свойство называется нетривиальным.
\end{define}

Мы не можем распознать множество языков так, как сами эти языки.
Причина в том, что обычный бесконечный язык нельзя записать в виде
цепочки конечной длины, которая может быть входом для некоторой МТ.
Вместо этого мы должны распознавать МТ, которые допускают эти языки.
Код самой МТ конечен, даже если язык, который она допускает,
бесконечен.
\begin{define}
  Пусть $\mathcal P$ --- это свойство РП-языков, а $L_{\mathcal P}$ ---
  множество кодов МТ $M_i$ таких, что $L(M_i)\in\mathcal P$. Тогда
  говорят, что свойство $\mathcal P$ разрешимо, если разрешим язык
  $L_{\mathcal P}$.
\end{define}
\begin{theorem}[Теорема Райса]
Всякое нетривиальное свойство РП-языков неразрешимо.
\end{theorem}

\end{document}
